This invention relates to programmable logic integrated circuits. In particular, the invention relates to a new architecture which provides for greater utility and flexibility of programmable logic devices ("PLDs"), and allows for programmable logic devices of much greater complexity than previously were possible.
The following references are background to this invention: Hartmann et al. U.S. Pat. No. 4,617,479; Hartmann et al. U.S. Pat. No. 4,609,986; Veenstra U.S. Pat. No. 4,677,318; Hartmann et al. U.S. Pat. No. 4,713,792; Birkner et al. U.S. Pat. No. 4,124,899; Cavlan U.S. Pat. No. 4,703,206; Spencer U.S. Pat. No. 3,566,153; J. C. Leininger, "Universal Logic Module", IBM Technical Disclosure Bulletin, Vol. 13, No. 5, Oct. 1970, pp. 1294-95; Ronald R. Munoz and Charles E. Stroud, "Automatic Partitioning of Programmable Logic Devices", VLSI Systems Design Magazine , Oct. 1987, pp. 74-78, and 86; and E. Goetting et al., "A CMOS Electrically-Reprogrammable ASIC with Multi-Level Radom Logic Capabilities", 1986 IEEE International Solid State Circuits Conference (Proceedings), pp. 244, 245, 359, and 360. All of these references are hereby incorporated by reference herein.
Several approaches have been used for the architecture of programmable logic integrated circuits. Among these are the "programmable AND, fixed OR" structure (referred to as a PAL) used in the above-mentioned Birkner et al. patent. This architecture has the advantages of higher speed and a simpler structure. However, because it has a fixed number of "product terms" (hereinafter "P-terms") per OR logic function eight P-terms is typical of most current PAL products), and because these P-terms cannot be shared by neighboring OR gates, many P-terms are typically wasted. On the other hand, thee are occasions when eight P-terms are not enough to handle the more complex logic functions. Experience has shown that in a broad range of applications, eight P-terms is on average much more than enough, and yet it is also often insufficient. For example, FIG. 2 in the above-mentioned Munoz et al. article is a graph of P-term requirements for a relatively large sample of logic functions (Munoz et al. FIG. 2 is substantially reproduced herein as FIG. 1). Similar studies done by the assignee of the present invention arrive at roughly similar conclusions: namely, a large percentage of logical functions (on the order of 50 to 70 percent) require less than four P-terms. However, a relatively significant "tail" exists where eight P-terms is not enough.
One way to achieve higher P-term utilization is to provide "variable P-term distribution". In essence, this is an attempt to guess a mixture of P-term requirements such that some OR gates have few P-terms (e.g., four), and some have a relatively large number (e.g., 12 or 16). See, for example, above-mentioned U.S. Pat. No. 4,609,986. This partially solves the problem of P-term utilization, but it significantly increases the complexity of the software support task because each function must be examined and then, depending upon its demand for P-term resources, assigned to a specific macrocell which has the minimum resources needed to fulfill the required demand (this process is called "fitting"). However, even with variable P-term distribution, many P-terms are typically still wasted.
Another way in which this P-term allocation problem can be solved is suggested in the above-mentioned paper by Leininger. With this structure, the P-term array is viewed as an array of programmable NOR or NAND gates whose inputs are programmable. Functions which require more than a single P-term are broken into multi-level NAND (or NOR) functions. Each level of (e.g., NAND) logic takes one P-term. Using this type of array, even quite complex logic functions can be done in a few levels of NAND logic. Again, however, there are some drawbacks. First, it is very likely that most logic functions will take more than a single P-term. This means that most often, several passes through the array will be required, and this causes a slowing down of evaluation of the function. Second, each P-term must feed back into the array input section. Thus, as the number of P-terms grows, so does the number of input lines. Even for arrays of modest complexity, the number of input signal lines (sometimes called "word lines") becomes excessive. For example, the part described in the above-mentioned IEEE ISSCC paper has only eight macrocells but has nearly 100 word lines, while a PAL circuit of similar complexity has only half as many word lines. Each word line adds to the length (and therefore the parasitic capacitance) of all of the P-terms. Greater P-term length leads to slower signal propagation.
Finally, there are programmable logic arrays ("PLAs") of the type described in the above-mentioned Spencer patent. Most (if not all) functions can be accomplished in one pass through the "AND" array plus one pass through the "OR" array. However, even the simplest functions require these two array delays. Thus, compared to the PAL architecture, there is a speed penalty (at least for simple functions). This type of PLA circuit is also more complex to execute in silicon because of the need for interface buffering between the AND and the OR array, and because of the inherently more complex programming circuits needed to program the two arrays.
In prior art programmable logic devices, a major obstacle to increasing the logic density has been array sizes which increase as the "square" of the increase in the number of output functions. This is true because for complete generality, it is necessary that all output functions also feed back as inputs into the array. However, in practice, it has been observed that this is massive overkill. That is, on average, only some subset of functions needs to be fed back. One solution to this problem is to break a single large array into several smaller arrays with functional communication between the smaller array blocks. In prior at devices such as the EP1200 (see U.S. Pat. No. 4,609,986) and the EP1800 (both commercially available from Altera Corporation of Santa Clara, California), this interconnect between blocks was done in a fixed manner. That is, in a device with several array blocks, there is local feedback to an array block, and there are a certain fixed number of global feedback signals between array blocks. While this approach does serve to keep the array sub-blocks to reasonable size (both from a bit density and a speed point of view), it creates routing bottlenecks between blocks. For example, in the Altera EP1800, there are four array blocks each with 12 flip-flop macrocells. Only four macrocell outputs from each array block are routed as global inputs to the other blocks. This bottleneck causes significant restrictions in allowing logic functions to "fit" within a device even though there are enough other resources (such as flip-flops, I/O pins, etc.).
In view of the foregoing, it is an object of this invention to provide an architecture for programmable logic devices which allows for the implementation of PLDs of much greater complexity.
It is another object of the invention to maximize the utilization of P-terms in PLDs.
It is a further object of the invention to make PLDs of high complexity that can operate at high speed.
It is a further object of the invention to provide for multiple logic array blocks ("LABs" ) which can operate independently or in concert, and to provide for a programmable interconnect array ("PIA") structure which allows for ease of communication between these array blocks.
It is a further object of the invention to provide a macrocell which is simpler and provides for increased functionality.
It is a further object of the invention to provide a regular, repeatable architecture which will be easy for a user to understand and easy for software tools to support.
It is a further object of the invention to provide for a modular architecture which allows for ease in constructing a family of products simply by reducing or increasing the number of LABs and the associated PIA structure.
It is a further object of the invention to allow for package bonding options such that some of the I/O pins are not bonded out, thus allowing high density PLDs to be put into relatively low pin-count packages.